package leetcode.programmer;

// 面试题 10.05. 稀疏数组搜索
public class FindString {


    public int findString(String[] words, String s) {
        int res = -1;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(s)) {
                res = i;
                break;
            }
        }

        return res;
    }

    @SuppressWarnings("all")
    // 二分, 由于有特殊字符，所以要处理掉
    public int findString2(String[] words, String s) {
        int left = 0;
        int right = words.length - 1;
        int res = -1;
        while (left < right) {
            int mid = left + right >> 1;
            while (mid > left && words[mid].isEmpty()) {
                //
                mid--;
            }
            if (words[mid].equals(s)){
                return mid;
            }else if (words[mid].compareTo(s)>0){
                    right = mid-1;
            }else {
                left = mid+1;
            }
        }
        return -1;
    }
}
